package sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort implements Sort {

    @Override
    public void sort(Comparable[] array) {
        shuffle(array);
        quickSort(array, 0, array.length - 1);
    }

    public void sort(Comparable[] array, boolean improved) {
        shuffle(array);
        quickSort3Way(array, 0, array.length - 1);
    }

    /**
     * The original quick sort without any algorithmic improvement
     *
     * @param array
     * @param lo
     * @param hi
     */
    public void quickSort(Comparable[] array, int lo, int hi) {
        if (hi <= lo + 15) {
            InsertionSort insert = new InsertionSort();
            insert.insertionSort(array, lo, hi);//to cover the situation that partPoint - 1 may be smaller than 0 which is outOfIndex
            return;
        }
        int partPoint = partition(array, lo, hi);
        quickSort(array, lo, partPoint - 1);
        quickSort(array, partPoint + 1, hi);

    }

    public int partition(Comparable[] arr, int lo, int hi) {
        Comparable partValue = arr[lo];
        for (int i = lo; i <= hi; ) {
            if (SortCommon.less(arr[i], partValue)) {
                SortCommon.swap(arr, i, lo);
                i++;
                lo++;
            } else if (arr[i] == partValue) {
                i++;
            } else {
                SortCommon.swap(arr, i, hi);
                hi--;
            }
        }
//        SortCommon.swap(arr, j, lo);
        return lo;
    }

    public int less(int a, int b) {
        return 0;
    }

    public void shuffle(Comparable[] arr) {
        Random rGen = new Random();
        int i = 0;
        while (i < arr.length) {
            int randIndex = rGen.nextInt(arr.length);
            SortCommon.swap(arr, i++, randIndex);
        }
    }

    public void quickSort3Way(Comparable[] arr, int lo, int hi) {

    }

    public static void main(String[] args) {
        QuickSort qSort = new QuickSort();
        Comparable[] arr = new Integer[]{4, 2, 3, 4, 4, 8, 1, 5};
        qSort.sort(arr);
        Arrays.stream(arr).forEach(e -> System.out.println(e));
    }

}
